package com.example.demo.leetcode;

import org.junit.jupiter.api.Test;

/**
 * 最长回文字符串
 * https://leetcode.cn/problems/longest-palindromic-substring/description/?envType=study-plan-v2&envId=top-interview-150
 */
public class LongestPalindrome {

    @Test
    public void longestPalindromeTest() {
        String s1 = longestPalindrome1("ccc");
        String s2 = longestPalindrome2("121324242313");
        // String s2 = longestPalindrome2("ccc");
        System.out.println(s1);
        System.out.println(s2);
    }

    /**
     * 中心扩散法
     */
    public String longestPalindrome1(String s) {
        if (s == null || s.length() < 2) return s;
        String res = s.substring(0, 1);
        for (int i = 0; i < s.length(); i++) {
            String oddStr = centerSpread(s, i, i);
            String evenStr = centerSpread(s, i, i + 1);
            String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
            if (maxLenStr.length() > res.length()) {
                res = maxLenStr;
            }
        }
        return res;
    }

    public String centerSpread(String s, int left, int right) {
        // left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
        // right = left + 1 的时候，此时回文中心是两个字符的中心，回文串的长度是偶数

        while (left >= 0 && right < s.length()) {
            if (s.charAt(left) == s.charAt(right)) {
                left--;
                right++;
            } else {
                break;
            }
        }

        return s.substring(left + 1, right);
    }

    /**
     * 动态规划
     * dp[i][j]表示S[i]至S[j]所表示的子串是否是回文子串，是则为1，不是为0。
     * 若S[i]!=S[j]，那S[i]至S[j]一定不是回文子串，dp[i][j] = 0
     * 若S[i]=S[j],那么只要S[i+1]和S[j-1]是回文子串，dp[i][j] = 1
     */
    public String longestPalindrome2(String s) {
        if (s == null || s.length() < 2) return s;
        int len = s.length();
        int[][] dp = new int[len][len];
        String res = s.substring(0, 1);

        for (int i = 0; i < len; i++) {
            dp[i][i] = 1;  // 单个字符串肯定是回文
            if (i < len - 1) { // 例如 aa
                if (s.charAt(i) == s.charAt(i + 1)) {
                    dp[i][i + 1] = 1;
                    String sub = s.substring(i, i + 2);
                    res = sub.length() > res.length() ? sub : res;
                }
            }
            if (i < len - 2) { // 例如 aba
                if (s.charAt(i) == s.charAt(i + 2)) {
                    dp[i][i + 2] = 1;
                    String sub = s.substring(i, i + 3);
                    res = sub.length() > res.length() ? sub : res;
                }
            }
        }

        //子串长度从4位开始，最长为整个字符串的长度
        for (int L = 4; L <= len; L++) {
            // 遍历字符串的起点，比如字符总长为10 子串长为3时，他的起点最大为7
            for (int i = 0; i < len + 1 - L; i++) {
                int j = L + i - 1;
                if (s.charAt(i) == s.charAt(j) && dp[i + 1][j - 1] == 1) {
                    // 说明这四个字符串是回文
                    dp[i][j] = 1;
                    String sub = s.substring(i, i + L);
                    res = sub.length() > res.length() ? sub : res;
                }
            }
        }

        return res;
    }
}
